package leecode

func largestRectangleArea(heights []int) int {
	//右边第一个比它小的元素 栈内元素顺序 从大到小 , 即栈顶的元素是最大元素的下标
	stack := make([]int, 0)
	heights = append([]int{0}, heights...)
	heights = append(heights, 0)
	stack = append(stack, 0)
	var result int
	for i := 1; i < len(heights); i++ {
		topIndex := stack[len(stack)-1] //栈顶元素的下标
		//如果当前元素小于栈顶元素
		if heights[i] < heights[topIndex] {
			for len(stack) != 0 && heights[i] < heights[topIndex] {
				//首先弹出栈顶元素
				stack = stack[:len(stack)-1]
				if len(stack) != 0 {
					h := heights[topIndex] //以哪一个柱子为基准,就用哪个柱子的高
					w := i - stack[len(stack)-1] - 1
					result = max(result, h*w)
					topIndex = stack[len(stack)-1]
				}
			}
			stack = append(stack, i)
		} else {
			stack = append(stack, i)
		}
	}
	return result
}
